1. Field of the Invention
The present invention is directed to a method for computer-supported motion estimation for picture elements of chronologically following images of a video sequence.
2. Description of the Prior Art
In the field of block-based image coding methods, and object based image coding methods as well, a qualitatively high-grade motion estimate for the blocks or, respectively, objects of the individual images of a video sequence is important in order to achieve a high quality of the reconstructed images at the receiver of the video data stream with an optimally high saving in required transmission capacity.
Instead of having to code the luminance information and/or chrominance information of the individual picture elements (pixels) of the images of a video sequence, motion estimation makes it possible to encode only the form or shape of specific blocks, or only the form or shape of specific objects, as well as further information with respect to the blocks or objects between two successive images, the encoded blocks or objects and information being transmitted to the receiver.
For example, the further information can identify the shift of these blocks or objects between two successive images.
A considerable savings in the required transmission capacity is achieved with this block-based or object-based coding.
Fundamentals about motion estimation in block-based image coding methods may be found, for example, in the following documents: R. Mester and M. Hotter, Zuverlassigkeit und Effizienz von Verfahren zur Verschiebungsvektor-schatzung, Mustererkennung, 1995, Informatik Aktuell, Springer Verlag, pp.285-294; Liu et al., Method and Apparatus for determining motion vectors for image sequences, U.S. Pat. No. 5,398,068, 1995; F. Dufaux and F. Mschehni, Motion Techniques for digital TV: A Review and a New Contribution, Proceedings of the IEEE, Vol. 83, No. 6, pp.858 through 876, June 1995.
A dynamic programming method is known from H. Sakoe et al., Dynamic Programming Algorithm Optimization for Spoken Word Recognition, IEEE Transactions, Vol. ASSP-26, No.1, pp.43 through 49, 1978.
The use of the dynamic programming method (Dynamic Programming Algorithm, DP method) is also known in image processing and particularly in conjunction with so-called stereo correspondence (D. Geiger et al., Occlusions and Binocular Stereo, Intern. Journal of Computer Vision, No.14, Kluwer Academic Publishers, Boston, pp.211 through 226, 1995).
One disadvantage in this method is that the cost function employed in the DP method is fashioned such that the motion vectors allocated to the picture elements are intensified in such a way that the motion vectors have no large differences within a uniform surface or area, i.e. within an object to be classified, so that no large discontinuities occur between the motion vectors (monotonicity constraint). Although a qualitatively good motion estimation is thereby achieved for the picture elements within the object, this method is inadequate especially for picture elements at the edges of objects, since these picture elements are not classified as object edge elements or points in this method but--erroneously--as occlusions.
Another method that employs the DP algorithm for motion estimation in the framework of stereo correspondence is known from I. Cox et al., Stereo Without Regularization, NEC Research Institute, Princeton, N.J. 08540, pp. 1-31,1992.
The two methods described above also have the disadvantage that the DP method is only implemented in a two-dimensional optimization space. This means that only the motion of objects in one direction is reliably recognized, for example in the direction of the investigated scan line. When, however, an object moves rapidly in another direction, then, as set forth below, it can occur that the object is no longer "found" by the DP method, and thus faulty motion vectors are allocated to the individual picture elements by this method.